// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

// 该文件包含计算支配树的代码
// 控制流图的。

// postorder计算对象的postorder遍历顺序
// f中的基本块。无法访问的块将不会出现。
func postorder(f *Func) []*Block {
	return postorderWithNumbering(f, nil)
}

type blockAndIndex struct {
	b     *Block
	index int // index是已探索的b的后续边数。
}

// PostOrderWithNumber提供DFS后序。
// 这似乎使循环查找更加健壮。
func postorderWithNumbering(f *Func, ponums []int32) []*Block {
	seen := make([]bool, f.NumBlocks())

	// 结果排序
	order := make([]*Block, 0, len(f.Blocks))

	// 一堆块和下一个要访问的子对象
	// 常量绑定允许对其进行堆栈分配。32是
	// 足以覆盖几乎所有的邮购电话。
	s := make([]blockAndIndex, 0, 32)
	s = append(s, blockAndIndex{b: f.Entry})
	seen[f.Entry.ID] = true
	for len(s) > 0 {
		tos := len(s) - 1
		x := s[tos]
		b := x.b
		if i := x.index; i < len(b.Succs) {
			s[tos].index++
			bb := b.Succs[i].Block()
			if !seen[bb.ID] {
				seen[bb.ID] = true
				s = append(s, blockAndIndex{b: bb})
			}
			continue
		}
		s = s[:tos]
		if ponums != nil {
			ponums[b.ID] = int32(len(order))
		}
		order = append(order, b)
	}
	return order
}

type linkedBlocks func(*Block) []Edge

const nscratchslices = 7

// 在实验上，具有512个或更少块的函数
// 占主导计算内存（大小）分配的75%
// 在make.bash中。
const minscratchblocks = 512

func (cache *Cache) scratchBlocksForDom(maxBlockID int) (a, b, c, d, e, f, g []ID) {
	tot := maxBlockID * nscratchslices
	scratch := cache.domblockstore
	if len(scratch) < tot {
		// req=最小值（1.5*tot，1.5*MinsCratchBlock）
		// 50%的填充允许图形在后期增长。
		req := (tot * 3) >> 1
		if req < nscratchslices*minscratchblocks {
			req = nscratchslices * minscratchblocks
		}
		scratch = make([]ID, req)
		cache.domblockstore = scratch
	} else {
		// 清除尽可能多的划痕，因为我们将（重新）使用
		scratch = scratch[0:tot]
		for i := range scratch {
			scratch[i] = 0
		}
	}

	a = scratch[0*maxBlockID : 1*maxBlockID]
	b = scratch[1*maxBlockID : 2*maxBlockID]
	c = scratch[2*maxBlockID : 3*maxBlockID]
	d = scratch[3*maxBlockID : 4*maxBlockID]
	e = scratch[4*maxBlockID : 5*maxBlockID]
	f = scratch[5*maxBlockID : 6*maxBlockID]
	g = scratch[6*maxBlockID : 7*maxBlockID]

	return
}

func dominators(f *Func) []*Block {
	preds := func(b *Block) []Edge { return b.Preds }
	succs := func(b *Block) []Edge { return b.Succs }

	// TODO:基准测试，并尝试查找在
	// 支配者简单与支配者LT
	return f.dominatorsLTOrig(f.Entry, preds, succs)
}

// dominatorsLTOrig运行Lengauer Tarjan以计算从
// 输入并使用predFn/succFn查找前辈/后辈以允许
// 计算支配树和后支配树。
func (f *Func) dominatorsLTOrig(entry *Block, predFn linkedBlocks, succFn linkedBlocks) []*Block {
	// 直接改编自原始TOPLAS文章的“简单”算法

	maxBlockID := entry.Func.NumBlocks()
	semi, vertex, label, parent, ancestor, bucketHead, bucketLink := f.Cache.scratchBlocksForDom(maxBlockID)

	// 此版本在大多数计算中使用整数，
	// 使工作数组更小且无指针。
	// fromID将ID转换为*块，在需要的地方。
	fromID := make([]*Block, maxBlockID)
	for _, v := range f.Blocks {
		fromID[v.ID] = v
	}
	idom := make([]*Block, maxBlockID)

	// 第一步。对问题图进行深度优先搜索。数字
	// 搜索过程中到达的顶点从1到n。
	n := f.dfsOrig(entry, succFn, semi, vertex, label, parent)

	for i := n; i >= 2; i-- {
		w := vertex[i]

		// TOPLAS纸中的步骤2
		for _, e := range predFn(fromID[w]) {
			v := e.b
			if semi[v.ID] == 0 {
				// 跳过不可到达的前置
				// 不是原始版本，但我们使用现有的pred，而不是构建一个。
				continue
			}
			u := evalOrig(v.ID, ancestor, semi, label)
			if semi[u] < semi[w] {
				semi[w] = semi[u]
			}
		}

		// 将w添加到桶[vertex[semi[w]]]
		// 机具铲斗作为已实施的链表
		// 在一对数组中。
		vsw := vertex[semi[w]]
		bucketLink[w] = bucketHead[vsw]
		bucketHead[vsw] = w

		linkOrig(parent[w], w, ancestor)

		// TOPLAS纸张中的步骤3
		for v := bucketHead[parent[w]]; v != 0; v = bucketLink[v] {
			u := evalOrig(v, ancestor, semi, label)
			if semi[u] < semi[v] {
				idom[v] = fromID[u]
			} else {
				idom[v] = fromID[parent[w]]
			}
		}
	}
	// toplas纸张中的步骤4
	for i := ID(2); i <= n; i++ {
		w := vertex[i]
		if idom[w].ID != vertex[semi[w]] {
			idom[w] = idom[idom[w].ID]
		}
	}

	return idom
}

// dfs从入口块开始对块执行深度优先搜索
// （以任意顺序）。这是从
// Tarjan Lengauer TOPLAS原创文章。还车很重要
// 父级的值与原始算法的值相同。
func (f *Func) dfsOrig(entry *Block, succFn linkedBlocks, semi, vertex, label, parent []ID) ID {
	n := ID(0)
	s := make([]*Block, 0, 256)
	s = append(s, entry)

	for len(s) > 0 {
		v := s[len(s)-1]
		s = s[:len(s)-1]
		// 在v上递归

		if semi[v.ID] != 0 {
			continue // 已经访问
		}
		n++
		semi[v.ID] = n
		vertex[n] = v.ID
		label[v.ID] = v.ID
		// 祖先[v]已经为零
		for _, e := range succFn(v) {
			w := e.b
			// 如果它有一个dfnum，我们已经访问了它
			if semi[w.ID] == 0 {
				// 是的，w可以被推多次。
				s = append(s, w)
				parent[w.ID] = v.ID // 继续覆盖此内容，直到它被访问。
			}
		}
	}
	return n
}

// compressOrig是LT paper的“简单”压缩功能
func compressOrig(v ID, ancestor, semi, label []ID) {
	if ancestor[ancestor[v]] != 0 {
		compressOrig(ancestor[v], ancestor, semi, label)
		if semi[label[ancestor[v]]] < semi[label[v]] {
			label[v] = label[ancestor[v]]
		}
		ancestor[v] = ancestor[ancestor[v]]
	}
}

// evalOrig是LT文件中的“简单”eval函数
func evalOrig(v ID, ancestor, semi, label []ID) ID {
	if ancestor[v] == 0 {
		return v
	}
	compressOrig(v, ancestor, semi, label)
	return label[v]
}

func linkOrig(v, w ID, ancestor []ID) {
	ancestor[w] = v
}

// 支配者计算f的支配者树。它返回一个切片
// 它将块ID映射到该块的直接控制者。
// 无法访问的块映射为零。入口块映射为nil。
func dominatorsSimple(f *Func) []*Block {
	// 现在有一个简单的算法
	// 库珀，哈维，肯尼迪
	idom := make([]*Block, f.NumBlocks())

	// 计算后序行走
	post := f.postorder()

	// 将块id映射到订单索引（用于intersect调用）
	postnum := make([]int, f.NumBlocks())
	for i, b := range post {
		postnum[b.ID] = i
	}

	// 使入口块成为自循环
	idom[f.Entry.ID] = f.Entry
	if postnum[f.Entry.ID] != len(post)-1 {
		f.Fatalf("entry block %v not last in postorder", f.Entry)
	}

	// 计算idom项的松弛
	for {
		changed := false

		for i := len(post) - 2; i >= 0; i-- {
			b := post[i]
			var d *Block
			for _, e := range b.Preds {
				p := e.b
				if idom[p.ID] == nil {
					continue
				}
				if d == nil {
					d = p
					continue
				}
				d = intersect(d, p, postnum, idom)
			}
			if d != idom[b.ID] {
				idom[b.ID] = d
				changed = true
			}
		}
		if !changed {
			break
		}
	}
	// 将入口块的idom设置为nil，而不是其自身。
	idom[f.Entry.ID] = nil
	return idom
}

// intersect找到b和c中最接近的支配者。
// 它需要所有块的后序编号。
func intersect(b, c *Block, postnum []int, idom []*Block) *Block {
	// TODO:此循环是O（n^2）。它曾用于nilcheck，
	// 请参阅BenchmarkNilCheckDeep*。
	for b != c {
		if postnum[b.ID] < postnum[c.ID] {
			b = idom[b.ID]
		} else {
			c = idom[c.ID]
		}
	}
	return b
}
